package com.iamk.segment;

//
//Union Find Data Structure of Tarjan for Disjoint Sets
//
public class UnionFind {

	int[] rank;
	int[] parent;

	//
	// Create a UF for n elements
	//
	UnionFind(int n) {
		int k;

		parent = new int[n];
		rank = new int[n];

//		System.out.println("Creating a UF DS for " + n + " elements");

		for (k = 0; k < n; k++) {
			parent[k] = k;
			rank[k] = 0;
		}
	}

	//
	// Find procedures
	//
	int Find(int k) {
		while (parent[k] != k)
			k = parent[k];
		return k;
	}

	//
	// Assume x and y being roots
	//
	int UnionRoot(int x, int y) {
		if (x == y)
			return -1;

		if (rank[x] > rank[y]) {
			parent[y] = x;
			return x;
		} else {
			parent[x] = y;
			if (rank[x] == rank[y])
				rank[y]++;
			return y;
		}
	}
}